package com.tree;

public class RedAndBlackImpl<T> implements RedAndBlack {

    private Node root;
    private static final boolean RED = true;
    private static final boolean BLACK = false;

    /*判断 key 是否存在*/
    public boolean isValid(int key) {
        return getValue(key) == null;
    }

    /*查找 key 对应的value
     */
    @Override
    public T getValue(int key) {
        Node node = root;
        return getValue(node, key);
    }

    private T getValue(Node node, int key) {
        if (node == null) {
            return null;
        }
        if (key < node.key && !isRed(node.left)) {
            return getValue(node.left, key);
        } else if (key > node.key) {
            return getValue(node, key);
        } else if (key < node.key && key < node.left.key && isRed(node.left)) {
            return getValue(node.left.left, key);
        } else if (key < node.key && isRed(node.left) && key > node.left.key) {
            return getValue(node.left.right, key);
        }
        return (T) node.value;
    }


    /*插入算法: (有两种情况)
     * 向一颗 2- 节点中插入: 可能向左插入,可能向右插入
     * 向一颗 3- 节点中插入: 可能向左插入,可能向中间插入,可能向右插入
     */
    @Override
    public void put(int key, Object value) {
        root = put(root, key, (T) value);
        root.color = BLACK;
    }

    private Node put(Node node, int key, T value) {
        if (node == null) {
            return new Node(key, 1, value, RED);
        }
        //将 key 找到合适的位置
        if (key < node.key) {
            put(node.left, key, value);
        } else if (key > node.key) {
            put(node.right, key, value);
        } else {
            //node.key = key,此时覆盖value
            node.value = value;
        }
        /*执行到这里时,节点已经插入完成.现在需要平衡整个红黑二叉树
         *在插入中会遇到的三种情况,如果暂时无法理解,可以自己画一个 3-2 树*/
        if (isRed(node.right) && !isRed(node.left)) {//表明根节点小于右子树的节点,出现在向 2- 树的右子树中插入节点的情况
            node = rotateLeft(node);
        }
        if (isRed(node.left) && isRed(node.left.left)) {//出现在向 3- 中插入最小节点
            node = rotateRight(node);
        }
        if (isRed(node.left) && isRed(node.right)) {//出现在向 3- 中插入key为中间值或最大值的情况
            flipColor(node);
        }
        node.num = node.left.num + node.right.num + 1;
        return node;
    }


    /*颜色转换 : 将两个子节点的红链接变为 根节点的红链接+两个子节点的黑链接*/
    private void flipColor(Node node) {
        node.color = RED;
        node.left.color = BLACK;
        node.right.color = BLACK;
    }

    /*左旋转 : 将红色的右链接变为左链接*/
    private Node rotateLeft(Node node) {
        Node rightNode = node.right;
        int rightNodeLeftNum = rightNode.left.num;
        node.right = rightNode.left;
        rightNode.left = node;
        rightNode.color = node.color;
        node.color = RED;
        rightNode.num = node.num;
        node.num = 1 + node.left.num + rightNodeLeftNum;
        return rightNode;
    }

    /*右旋转 : 将红色的左链接变为右链接*/
    private Node rotateRight(Node node) {
        Node leftNode = node.left;
        int leftNodeRightNum = leftNode.right.num;
        node.left = leftNode.right;
        leftNode.right = node;
        leftNode.color = node.color;
        node.color = RED;
        leftNode.num = node.num;
        node.num = 1 + node.right.num + leftNodeRightNum;
        return leftNode;
    }


    boolean isRed(Node node) {
        return node != null && node.color == RED;
    }

    class Node<T> {
        Node left, right;
        int key;    //相当于是键值 key,这里为了简单,就写为 int
        T value;
        int num;    //这颗子树中的节点个数
        boolean color;  //当前节点的颜色表示的含义是 : 指向当前节点的链接的颜色(红:true,黑:false)

        Node(int key, int N, T value, boolean color) {
            this.key = key;
            this.value = value;
            this.num = N;
            this.color = color;
        }
    }
}
